1. Field of the Invention
The present invention pertains to the field of data transfer in a computer system. More particularly, this invention relates to transfer of data between multiple buses using bus bridges.
2. Background
Modem computer systems generally include multiple agents, such as microprocessors, storage devices, display devices, etc. which are interconnected via a system bus. The system bus operates to transfer address, data and control signals between these agents. Some modem computer systems employ multiple buses, in which various agents are coupled to one or more buses. Typically, each agent is coupled to a single bus.
Bus bridges are often utilized in multiple-bus systems to connect the buses and thereby allow agents coupled to one bus to access agents coupled to another bus. The function of the bridge typically involves transferring commands between two buses. The commands transferred by the bus bridge frequently have data associated with them (e.g., read or write commands).
One problem which frequently arises in computer systems with multiple agents is the need to preserve transaction ordering. Support for transaction ordering implies that if an agent writes to location A in memory followed by a write to location B in memory, another agent cannot read the new data in location B and stale (i.e., old) data in location A. A number of software algorithms require a producer-consumer relationship and thus depend on this support to ensure proper functionality. For example, in a system comprising multiple processors, assume that processor P1 is a producer of information and processor P2 is a consumer of information. P1 performs a write operation W1 to location 1 followed by a write operation W2 to location 2. Location 2 contains a flag variable that signals that the data in location 1 is valid. Processor P2 continuously performs a read operation R2 on location 2 until the flag becomes valid. After the flag is observed valid, P2 performs a read operation R1 on location 1 to read the data. In order for this algorithm to successfully execute in a multiprocessor system, the order in which W1 and W2 are written by processor P1 should be the same order in which R1 and R2 appear to be updated to processor P2.
A bus bridge in a multiple-bus system must address the problem of transaction ordering. In the example above, processors P1 and P2 may be coupled to one bus while locations 1 and 2 are coupled to a second bus, and a bus bridge is supporting access between the two buses. Thus, the bus bridge must ensure that transaction ordering is maintained. That is, the order in which W1 and W2 are written by an agent(s) should be maintained by the bus bridge.
One method of maintaining transaction ordering is shown in FIG. 1. A bus bridge 100 is shown which interfaces between two buses: a first system bus 102 and a second system bus 104. An agent 130 is coupled to system bus 102 and an agent 140 is coupled to system bus 104. In this system, bus bridge 100 contains a first queue 110 which contains requests issued on system bus 102 which target an agent on system bus 104. Bus bridge 100 also contains a second queue 115 which contains requests issued on system bus 104 which target an agent on system bus 102. A temporary storage buffer 120 may also be contained in bridge 100.
Bridge 100 transfers commands between buses 102 and 104. For example, assume agent 130 issues a request targeting agent 140. This request is received by bridge 100 and placed in queue 110. Alternatively, if agent 140 issues a request targeting agent 130, the request is placed in queue 115.
Data transferred between buses is stored in temporary storage buffer 120. For example, a read request placed into queue 110 is executed on system bus 104. When the target agent responds, the read data is placed in temporary storage buffer 120. The agent issuing the original request then knows the data to satisfy its request is contained in temporary storage buffer 120.
In the prior art system shown, both queues 110 and 115 contain pending requests and transfer the requests onto the appropriate buses. When a write request is issued by either agent 130 or agent 140, bridge 100 forces transaction ordering by preventing any read transactions from being placed in the opposite queue until the queue with the write request is flushed (i.e., the write transaction is executed on the targeted bus). For example, if a write operation were placed in queue 115, bridge 100 would prevent any read operations from being placed in queue 110 until queue 115 is flushed.
Although this prior art method effectively resolves the transaction ordering problem, it does not do so efficiently because it prevents the use of one queue while the other is being flushed. As described above, transactions are not placed in one queue while the other queue contains a write operation.
Thus, it would be advantageous to provide a system which resolves the transaction ordering problem in an effective and efficient manner. The present invention provides such a solution.
In addition to maintaining transaction ordering, the bus bridge should also avoid deadlock situations within the bridge. Deadlock situations typically require at least a temporary suspension of system operation, if not an entire system reset. A deadlock situation arises, for example, if the bridge contains two requests, one targeting an agent on the first bus and the second targeting an agent on the second bus, and neither request can be executed until the other is satisfied. Thus, the deadlock prevents the bridge from operating properly.
Thus, it would be advantageous to provide a system which prevents the occurrence of deadlocks within the bus bridge, while at the same time maintaining efficient operation. As will be seen, the present invention provides such a solution.